package threesum

import "sort"


func threeSum(nums []int) [][]int {
	// 双指针法，a确定时，双指针确定b c
	sort.Ints(nums)
	var res [][]int
	// var a,b,c int
	var n int = len(nums)
	for i:=0;i<n-2;i++{
		if nums[i]>0 {
			break  //后面不可能有负值
		}
		// 判断a 是否枚举过
		if i>0 && nums[i] == nums[i-1] {
			//不是第一次出现，就是已经枚举guo
			continue
		}
		// 枚举b+c=-a
		target := 0- nums[i]
		k := n-1
		for j:=i+1;j<n;j++{
			//判断b是否枚举过
			if j>i+1 && nums[j]==nums[j-1] {
				continue
			}
			for j < k && nums[j]+nums[k] > target {
				//偏大
				k -- 
			}
			// 判断下j k 的关系
			if j==k {
				// 那么此时nums[j]+nums[k]都会大于target
				break  // 不要考虑b增加的情况
			}
			if nums[j]  + nums[k] == target {
				res = append(res, []int{nums[i],nums[j],nums[k]})
			}
		}

	}
	return res
}